package listbyorder.access001_100.test42;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/31 15:58
 */
public class Solution1 {

    // 方法一：用两个数组分别记录每个位置左边的最大高度和右边的最大高度
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;
        int ans = 0;
        int len = height.length;
        int[] l_max = new int[len];
        int[] r_max = new int[len];
        l_max[0] = r_max[0] = 0;
        l_max[len - 1] = r_max[len - 1] = 0;
        for (int i = 1; i < height.length - 1; i++) {
            l_max[i] = Math.max(l_max[i - 1], height[i - 1]);
            r_max[len - i - 1] = Math.max(r_max[len - i], height[len - i]);
        }
        for (int i = 1; i < len - 1; i++) {
            int cur_h = Math.min(l_max[i], r_max[i]);
            ans += cur_h > height[i] ? cur_h - height[i] : 0;
        }
        return ans;
    }
}
